/* 同余
* 1.拓展欧几里得算法
    (a,b) = d;
    ax0 + by0 = d

    x = x0 + k(a/d)
    y = y0 - k(b/d)

    ax = 1(mod b)

    ax = (b, a mod b)

* 2.欧拉定理
    1ex = 1 (mod c)
    -> a^(phi(n)) = 1 (mod n) && (a,n)互质
        且满足上述式子的最小正整数x一定是phi(c)的约数，即x|phi(c)


* 本题:
    L|88...8 x位
    -> x * 1...11 x位
    -> x * 9...99/9 x位
    -> x * 1ex-1/9 

    9L|8*(1ex-1)
    -> 9/8*L|(1ex-1)
    -> 1ex = 1 (MOD c) c=9/8
    mex + n * c = 1
    -(欧拉定理)-> x,c互质 -> 1ephi(c) = 1 (mod c) 
*/

#define DEBUG
#pragma GCC optimize("O1,O2,O3,Ofast")
#pragma GCC optimize("no-stack-protector,unroll-loops,fast-math,inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,ssse3")

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define int long long

//欧几里得算法
inline int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

int get_euler(int C) //欧拉函数phi(n): <=C的正整数中与n互质的数的个数
{
    int res = C;
    for(int i = 2; i <= C / i; i++) {
        if(C % i == 0) {
            while(C % i == 0) C /= i;
            res = res / i * (i-1); // res *(1- 1/i)
        }
    }
    if(C > 1) res = res / C * (C-1); //C本身就是个质数
    return res;
}

//龟速乘
int qmul(int base1, int base2, int MOD) //base1 * base2
{
    int res = 0;
    while(base2) {
        if(base2 & 1) res = (res + base1) % MOD;
        base1 = (base1 + base1) % MOD;
        base2 >>= 1;
    }
    return res;
}
int qmi(int base, int index, int MOD)
{
    int res = 1;
    while(index)
    {
        if(index&1) res = qmul(res, base, MOD); //直接乘爆long long
        base = qmul(base, base, MOD);
        index >>= 1;
    }
    return res;
}

signed main()
{
    #ifdef DEBUG
        freopen("./in.txt", "r", stdin);
    #else
        ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #endif

    int L, T = 1;
    while(cin >> L, L)
    {
        int C = 9 * L / gcd(L, 8); //L*9/8 但是不能直接/, 避免精度丢失
        //但是这样计算的结果是2或4拼接，不影响最终答案(乘到8就可以)
        int phi = get_euler(C);


        int res = 1e18;
        if(C%2==0 || C%5==0) res = 0;//C与10不互质
        else {
            for(int d = 1; d*d<=phi; d++) //枚举phi(C)的约数
                if(phi%d == 0)
                {
                    if(qmi(10, d, C) == 1) res = min(res, d);
                    if(qmi(10, phi/d, C) == 1) res = min(res, phi / d);
                }
        }
        

        printf("Case %d: %lld\n", T++, res);

    }
    return 0;
}